package com.itzmn.examinations.shumeikeji;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

/**
 * @Author: 张梦楠
 * @Date: 2019/1/16 21:04
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 数美科技笔试题
 */
public class Class2 {

    public static void main(String[] args) {
        new Class2().init();
    }

    private void init() {
        int a = -2;
        System.out.println(Integer.toBinaryString(a));

        System.out.println(binary_to_integer("0101"));
//        search();
    }

    /**
     * 1.将给定的二进制字符串转成十进制
     * @param binary
     * @return
     */
    int binary_to_integer(String binary) {
        int i=0;
        String[] split = binary.split("");
        int i1 = Integer.parseInt(split[0]);
        for (int j=split.length-1;j>0;j--){
            i += Integer.parseInt(split[j]) * Math.pow(2,split.length-j-1);
        }
        return i1 == 0 ? i : -1*i;
    }


    /**
     * 2.给定一个有序数组，从某处截断，放到数组首位，传入，查找某个数
     *  1,2,3,4,5
     *  4,5,1,2,3
     * @param a 截断后的数组
     * @param x
     * @return
     *
     */
    int search(int[] a, int x) {
        int s = s(a, x, 0, a.length-1);
        return s;
    }
    /**
     * @param a 数组
     * @param x 值
     * @param l 数组左边界
     * @param r 数组右边界
     * @return
     */
    int s(int[] a,int x,int l,int r){
        int re = -1;
        int i = r - l;
        if (r < l){
            return -1;
        }
        int i1 = i / 2 + l;
        // 左边比右边大
        if (a[l] > a[r]){
            if (a[l] == x){
                return l;
            }
            if (a[i1] < x){
                re = s(a,x,i1+1,r);
            }else {
                re = s(a,x,l,i1-1);
            }
            // 左边比右边小
        }else {
            if (a[l] == x){
                return l;
            }
            if (a[i1] < x){
                    re = s(a,x,i1+1,r);
            }else {
                re = s(a,x,l,i1-1);
            }
        }
        return re;
    }


    /**
     * 3.给定了一个公式，计算概率
     * @param xs
     * @return
     */
    double entropy(int[] xs) {

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<xs.length;i++){
            map.put(xs[i],map.containsKey(xs[i]) ? map.get(xs[i])+1 : 1);
        }
        Iterator<Integer> iterator = map.keySet().iterator();
        double re = 0;
        while (iterator.hasNext()){
            Integer next = iterator.next();
            Integer integer = map.get(next);
            double i = integer / xs.length;
            re += i * (Math.log(i) / Math.log(2));
        }
        return -1*re;
    }


    /**
     * 4.实现一个LRU的数据结构
     */
    class Records {
        int size = 0;
        long[] longs = null;
        public Records(int init){
            longs = new long[init];
        }
        int start = 0,end = 0;
        // 将当前事件时间戳ts添加到数据结构中
        // 添加数据，end指针加加，
        public void record(long ts){
            if (size == longs.length){
                //如果数组满了，将最初加入的覆盖掉
                start++;
            }else {
                size++;
            }
            longs[end] = ts;
            end = end == longs.length-1 ? 0 : end+1;
            start = start == longs.length-1 ? 0 : start+1;
        };

        // 获取下标为i的事件的时间戳ts，最后一个事件的下标是0，保证 i < N
        public long getLast(int i){
            // 如果获取的下标不存在，返回0
            if (i>size){
                return 0;
            }
            //得到要获取的下标
            int i1 = end - 1 - i;
            //如果是负数，说明end小于start，需要从数组后面取
            if (i1<0){
                // 加负数，相当于减少数
                return longs[longs.length + i1];
            }
            return longs[i1];
        };
    }


}
